﻿/*
输入：
4 5
1 2
2 4
3 4
4 5
输出：
10
*/
// 研究材料的种类n, 行李箱容量v
string[] nvArr = Console.ReadLine().Split(" ");
int n = int.Parse(nvArr[0]);
int v = int.Parse(nvArr[1]);

// 各个材料的重量和价值
int[] weightArr = new int[n];
int[] valueArr = new int[n];
for (int i = 0; i < n; i++)
{
    string[] wvArr = Console.ReadLine().Split(" ");
    weightArr[i] = int.Parse(wvArr[0]);
    valueArr[i] = int.Parse(wvArr[1]);
}

// 一维数组解决完全背包问题
int[] dp = new int[v + 1];
for (int i = 0; i < n; i++)
{
    for (int j = 0; j <= v; j++)
    {
        if (j >= weightArr[i]) dp[j] = Math.Max(dp[j], dp[j - weightArr[i]] + valueArr[i]);
    }
}

Console.WriteLine(dp[v]);